package leetcode.lt100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution_40 {

	public static void main(String[] args) {
		int[] candidates = { 10, 1, 2, 7, 6, 1, 5 };
		int target = 8;

		List<List<Integer>> res = 	new Solution_40().combinationSum2(candidates, target);
		
		System.out.println(res);
	}

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Set<List<Integer>> res = new HashSet<List<Integer>>();
		List<Integer> temp = new ArrayList<Integer>();
		// 排序
		Arrays.sort(candidates);
		dfs(res, temp, candidates, target, 0);
		List<List<Integer>> r = new ArrayList<List<Integer>>();
		r.addAll(res);
		return r;
	}

	private void dfs(Set<List<Integer>> res, List<Integer> temp, int[] candidates, int target, int start) {

		if (target == 0) {
			List<Integer> list = new ArrayList<Integer>();
			list.addAll(temp);
			res.add(list);
			return;
		}

		for (int i = start; i < candidates.length && candidates[i] <= target; i++) {
			temp.add(candidates[i]);
			dfs(res, temp, candidates, target -candidates[i], i + 1);
			temp.remove(temp.size() - 1);
		}

	}
}